﻿// Write a program that finds the sequence of maximal sum in given array. Example:
// {2, 3, -6, -1, 2, -1, 6, 4, -8, 8} -> {2, -1, 6, 4}
// Can you do it with only one loop (with single scan through the elements of the array)?

using System;

class FindSequenceOfMaximalSum
{
    static void Main()
    {
        // read array size
        uint arraySize;
        do
        {
            Console.Write("Enter array size: ");
        } while (!uint.TryParse(Console.ReadLine(), out arraySize));

        // read array elements
        int[] intArray = new int[arraySize];
        for (int i = 0; i < intArray.Length; i++)
        {
            do
            {
                Console.Write("Enter array elements {0}: ", i + 1);
            } while (!int.TryParse(Console.ReadLine(), out intArray[i]));
        }

        // Kadane's algorithm
        int sum = intArray[0];
        int maxSum = intArray[0];
        int sequenceLengthTemp = 1;
        int sequenceLength = 1;
        int startIndexTemp = 0;
        int startIndex = 0;

        for (int i = 1; i < intArray.Length; i++)
        {
            if (intArray[i] + sum > intArray[i])
            {
                sum += intArray[i];
                sequenceLengthTemp++;
            }
            else
            {
                sum = intArray[i];
                startIndexTemp = i;
                sequenceLengthTemp = 1;
            }

            if (sum > maxSum)
            {
                maxSum = sum;
                sequenceLength = sequenceLengthTemp;
                startIndex = startIndexTemp;
            }
        }

        // print result
        Console.Write("The sequence of maximal sum is: {");
        int endIndex = startIndex + sequenceLength;
        for (int i = startIndex; i < endIndex; i++)
        {
            Console.Write(intArray[i]);
            if (i != endIndex - 1)
            {
                Console.Write(", ");
            }
        }
        Console.WriteLine("}} = {0}", maxSum);
    }
}